package cn.camel.algorithm.BloomFilter;

import java.util.BitSet;
import java.util.Random;
import java.util.function.ToIntFunction;

/**
 * @author: Camel
 * @description: 布隆过滤器
 * @date: 2025/10/20 13:49
 */
public class BloomFilter<T> {
    private final BitSet bitSet;
    private final int size;
    private final int numHashFunctions;
    private final ToIntFunction<T>[] hashFunctions;

    public BloomFilter(int expectedElements, double falsePositiveRate) {
        // 计算最优位数组大小
        this.size = calculateSize(expectedElements, falsePositiveRate);
        // 计算最优哈希函数数量
        this.numHashFunctions = calculateNumHashFunctions(expectedElements, size);
        this.bitSet = new BitSet(size);
        this.hashFunctions = createHashFunctions(numHashFunctions);
    }

    // 添加元素
    public void add(T item) {
        for (ToIntFunction<T> hashFunction : hashFunctions) {
            int index = Math.abs(hashFunction.applyAsInt(item)) % size;
            bitSet.set(index);
        }
    }

    // 检查元素是否存在
    public boolean mightContain(T item) {
        for (ToIntFunction<T> hashFunction : hashFunctions) {
            int index = Math.abs(hashFunction.applyAsInt(item)) % size;
            if (!bitSet.get(index)) {
                return false;
            }
        }
        return true;
    }

    // 计算位数组大小
    private int calculateSize(int n, double p) {
        return (int) Math.ceil(-(n * Math.log(p)) / (Math.log(2) * Math.log(2)));
    }

    // 计算哈希函数数量
    private int calculateNumHashFunctions(int n, int m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }

    // 创建哈希函数（使用不同种子模拟多个哈希函数）
    @SuppressWarnings("unchecked")
    private ToIntFunction<T>[] createHashFunctions(int k) {
        Random random = new Random();
        ToIntFunction<T>[] functions = new ToIntFunction[k];
        for (int i = 0; i < k; i++) {
            int seed = random.nextInt();
            functions[i] = obj -> (obj.hashCode() ^ seed);
        }
        return functions;
    }

    // 获取当前误判率（近似值）
    public double estimateFalsePositiveRate() {
        double filledBits = (double) bitSet.cardinality() / size;
        return Math.pow(filledBits, numHashFunctions);
    }

    // 测试方法
    public static void main(String[] args) {
        // 创建布隆过滤器：预期10000个元素，误判率0.01
        BloomFilter<String> bloomFilter = new BloomFilter<>(10000, 0.01);

        // 添加元素
        bloomFilter.add("apple");
        bloomFilter.add("banana");
        bloomFilter.add("orange");

        // 测试存在元素
        System.out.println("Contains 'apple': " + bloomFilter.mightContain("apple")); // true
        System.out.println("Contains 'banana': " + bloomFilter.mightContain("banana")); // true

        // 测试不存在元素
        System.out.println("Contains 'grape': " + bloomFilter.mightContain("grape")); // false

        // 测试误判率
        int falsePositives = 0;
        int tests = 10000;
        for (int i = 0; i < tests; i++) {
            if (bloomFilter.mightContain("fruit" + i)) {
                falsePositives++;
            }
        }
        System.out.printf("实际误判率: %.4f%%\n", (falsePositives * 100.0) / tests);
        System.out.printf("预估误判率: %.4f%%\n", bloomFilter.estimateFalsePositiveRate() * 100);
    }
}
